package wheel.arithmetic;



import java.util.*;

/**
 * 败者树
 */
public class FailTree {

    Node rootNode;
    List<DataQueue> queues;

    public FailTree(List<DataQueue> queues) {
        //TODO 队列中的数是有序的。
        this.queues = queues;
        //TODO 应该验证列表中的队列不为空。
        createDataStruct();
    }


    private void createDataStruct() {
        List<Node> list = new ArrayList<>(queues.size());
        for(DataQueue queue : queues) {
            Node node = new Node();
            node.queue = queue;
            node.value = queue.poll();
            list.add(node);
        }

        while(list.size()!=1){

            List<Node> tempList = new ArrayList<>(list.size());
            Node left = null;
            for(Node node : list){
                if(left==null)
                    left = node;
                else if(left!=null){
                    Node right = node;
                    if(left.value <right.value) {
                        node = left;

                    }
                    Node parentNode = new Node();
                    parentNode.value = node.value;
                    parentNode.left = left; parentNode.right = right;
                    replenish(node, parentNode);
                    tempList.add(parentNode);
                    left = null;
                }
            }

            //节点单数的情况
            if(left!=null){
                Node parentNode = new Node();
                parentNode.value = left.value;
                parentNode.left = left;
                replenish(left, parentNode);
                tempList.add(parentNode);
            }

//            System.out.println(tempList);

            list = tempList;
        }

        if(list.size()==1)
            rootNode = list.get(0);
    }

    public void replenish(Node node, Node parentNode){
        node.value = null;
        if(node.left!=null && node.right!=null) {
            if (node.left.value < node.right.value) {
                node.value = node.left.value;
                replenish(node.left, node);
            } else {
                node.value = node.right.value;
                replenish(node.right, node);
            }
        }else if(node.left!=null || node.right!=null) {
            Node rNode = node.left !=null ? node.left : node.right;
            node.value = rNode.value;
            replenish(rNode, node);
        }else{
            //最低层节点
            if(node.queue!=null)
                node.value = node.queue.poll();

            //要断掉父节点指向当前节点的链接。
            if(node.value==null && parentNode!=null) {
                if (parentNode.left == node)
                    parentNode.left = null;
                else
                    parentNode.right = null;
            }
        }
    }

    public Long poll(){
        Long value = rootNode.value;
        //败局已定
        if(value==null)
            return null;
        replenish(rootNode, null);
        return value;
    }
}

class Node{
    Node left, right;
//    Node brother, parent;
    //最底层节点的必备
    DataQueue queue;
    //TODO 暂时是Long类型
    Long value;
}
